package cn.cxq.learning.recursion;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;

/**
 * 剑指offer
 * 矩阵中的路径
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M 热度指数：6774
 * 本题知识点： dfs
 * 算法知识视频讲解
 * 题目描述
 * 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 \begin{bmatrix} a & b & c &e \\ s & f & c & s \\ a & d & e& e\\ \end{bmatrix}\quad
 * ⎣
 * ⎡
 * ​
 * <p>
 * a
 * s
 * a
 * ​
 * <p>
 * b
 * f
 * d
 * ​
 * <p>
 * c
 * c
 * e
 * ​
 * <p>
 * e
 * s
 * e
 * ​
 * <p>
 * ⎦
 * ⎤
 * ​
 * 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
 * <p>
 * 示例1
 * 输入
 * 复制
 * [[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"
 * 返回值
 * 复制
 * true
 * 示例2
 * 输入
 * 复制
 * [[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcb"
 * 返回值
 * 复制
 * false
 * 备注:
 * 0 <= matrix.length <= 200
 * 0 <= matrix[i].length <= 200
 */
public class HasPath {

    int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 所有的方向
    boolean[][] isVisited; // 是否已经遍历过
    boolean flag = false; // 是否已经成功

    @Test
    public void test() {
        System.out.println(hasPath(new char[][]{{'a','b','c','e'},{'s','f','c','s'},{'a','d','e','e'}}, "seee"));
    }

    public boolean hasPath(char[][] matrix, String word) {

        if (word.length() == 0) {
            return true;
        }

        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        ArrayList<int[]> starts = new ArrayList<>(); // 存放所有的起点

        for (int x = 0; x < matrix.length; x++) {
            for (int y = 0; y < matrix[0].length; y++) {
                if (matrix[x][y] == word.charAt(0)) {
                    starts.add(new int[]{x,y});
                }
            }
        }

        if (starts.isEmpty()) {
            return false;
        }

        isVisited = new boolean[matrix.length][matrix[0].length];

        for (int[] start : starts) {
            go(start[0], start[1], matrix, word, isVisited, 1);
        }

        return flag;
    }

    private void go( int x, int y, char[][] matrix, String word, boolean[][] isVisited, int step) {

        if (flag) {
            return; // 不成功绝不返回，直到所有情况都遍历完成才可以返回
        }

        for (int i = 0; i < 4; i++) {
            goDirection(i,x,y,word,matrix,step);
        }

        if (step < word.length() && !flag) {
            isVisited[x][y] = false; // 如果四个方向都走完了无路可走就想着回溯，将痕迹清空然后从上一次的地方开始往下一个方向遍历
        } else {
            flag = true; // 如果不是走入绝境而是成功了那就直接将flag置为true。
        }
    }

    private void goDirection(int direction, int x, int y, String word, char[][] matrix, int step) {
        int nextX = x + directions[direction][0];
        int nextY = y + directions[direction][1];

        if (nextX >= 0 && nextX < matrix.length && nextY >= 0 && nextY < matrix[0].length && step < word.length() && matrix[nextX][nextY] == word.charAt(step)) {
            if (!isVisited[nextX][nextY]) {
                isVisited[nextX][nextY] = true;
                go(nextX, nextY, matrix, word, isVisited, step + 1);
            }
        }
    }
}
